package leet_code;

import java.util.*;

/**
 * 1、hash相关问题
 * https://leetcode.cn/studyplan/top-100-liked/
 */
public class A_1_HashQuestion {
    /**
     * https://leetcode.cn/problems/two-sum/?envType=study-plan-v2&envId=top-100-liked
     * 1. 两数之和
     * 给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target  的那 两个 整数，并返回它们的数组下标。
     * 你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
     * 你可以按任意顺序返回答案。
     *
     * 示例 1：
     * 输入：nums = [2,7,11,15], target = 9
     * 输出：[0,1]
     * 解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
     *
     * 示例 2：
     * 输入：nums = [3,2,4], target = 6
     * 输出：[1,2]
     *
     * 示例 3：
     * 输入：nums = [3,3], target = 6
     * 输出：[0,1]
     *
     *
     * 提示：
     * 2 <= nums.length <= 104
     * -109 <= nums[i] <= 109
     * -109 <= target <= 109
     * 只会存在一个有效答案
     *
     *
     * 进阶：你可以想出一个时间复杂度小于 O(n2) 的算法吗？
     */
    public int[] twoSum(int[] nums, int target) {
        return null;
    }

    /**
     * 49. 字母异位词分组
     * 给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
     * 字母异位词 是由重新排列源单词的所有字母得到的一个新单词。
     *
     * 示例 1:
     * 输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
     * 输出: [["bat"],["nat","tan"],["ate","eat","tea"]]
     *
     * 示例 2:
     * 输入: strs = [""]
     * 输出: [[""]]
     *
     * 示例 3:
     * 输入: strs = ["a"]
     * 输出: [["a"]]
     *
     * 提示：
     * 1 <= strs.length <= 104
     * 0 <= strs[i].length <= 100
     * strs[i] 仅包含小写字母
     */
    public List<List<String>> groupAnagrams(String[] strs) {
//        //将字符串转换为排序后的
//        Map<String, List<String>> map = new HashMap<>(16);
//        for (String str : strs) {
//            char[] chars = str.toCharArray();
//            Arrays.sort(chars);
//            String s = String.valueOf(chars);
//            if (map.containsKey(s)) {
//                List<String> strings = map.get(s);
//                strings.add(str);
//            } else {
//                ArrayList<String> tempStrs = new ArrayList<>();
//                tempStrs.add(str);
//                map.put(s, tempStrs);
//            }
//        }
//        return new ArrayList<>(map.values());
//  ------------------------------------------------------------------

        Map<String, List<String>> map = new HashMap<>(16);
        //仅记录字符串中各个字符的数量
        for (String str : strs) {
            char[] chars = str.toCharArray();
            int[] charNum = new int[26];
            for (char c : chars) {
                charNum[c - 97] += 1;
            }

            StringBuffer buf = new StringBuffer();
            for (int i = 0; i < charNum.length; i++) {
                if (charNum[i] == 0) {
                    continue;
                }
                buf.append(i).append(":").append(charNum[i]).append(",");
            }
            String  s = buf.toString();

            if (map.containsKey(s)) {
                List<String> strings = map.get(s);
                strings.add(str);
            } else {
                ArrayList<String> tempStrs = new ArrayList<>();
                tempStrs.add(str);
                map.put(s, tempStrs);
            }
        }
        return new ArrayList<>(map.values());
    }

    private boolean addGroup(List<String> item, String str) {
        if (item.size() == 0) {
            item.add(str);
            return true;
        }
        String first = item.get(0);
        char[] fChars = first.toCharArray();
        sortCharArr(fChars);
        char[] sChars = str.toCharArray();
        sortCharArr(sChars);
        if (Arrays.equals(fChars, sChars)) {
            item.add(str);
            return true;
        }
        return false;
    }



    private void sortCharArr(char[] chars){
        for (int i = 0; i < chars.length - 1; i++) {
            boolean swapped = false;
            // 进行一轮冒泡排序
            for (int j = 0; j < chars.length - i - 1; j++) {
                if (chars[j] > chars[j + 1]) {
                    char temp = chars[j];
                    chars[j] = chars[j + 1];
                    chars[j + 1] = temp;
                    swapped = true;
                }
            }
            if (!swapped) {
                break;
            }
        }
    }

    /**
     * 128. 最长连续序列
     * 给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
     * 请你设计并实现时间复杂度为 O(n) 的算法解决此问题。
     *
     * 示例 1：
     * 输入：nums = [100,4,200,1,3,2]
     * 输出：4
     * 解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。
     *
     * 示例 2：
     * 输入：nums = [0,3,7,2,5,8,4,6,0,1]
     * 输出：9
     *
     *
     * 提示：
     * 0 <= nums.length <= 105
     * -109 <= nums[i] <= 109
     */
    public int longestConsecutive(int[] nums) {
        nums = Arrays.stream(nums).distinct().toArray();
        Map<Integer, Integer> allNumMap = new HashMap<>(nums.length);
        for (int num : nums) {
            allNumMap.put(num,1);
        }

        int maxCount = 0;

        int tempCount = 0;
        for (int num : nums) {
            if (allNumMap.containsKey(num - 1)) {
                continue;
            }
            tempCount = 1;
            int temp = num + 1;
            while (allNumMap.containsKey(temp)) {
                tempCount +=1;
                temp++;
            }
            maxCount = Math.max(maxCount, tempCount);
        }
        return maxCount;
    }
    public static void main(String[] args) {
        A_1_HashQuestion thisO = new A_1_HashQuestion();
//        String[] str = {"eat", "tea", "tan", "ate", "nat", "bat"};
//        String[] str = {"a"};
//        long star = System.currentTimeMillis();
//        List<List<String>> lists = thisO.groupAnagrams(str);
//        System.out.println(lists.toString());
//        long end = System.currentTimeMillis();
//        System.out.println(end - star);
          int[] ints = {0,3,7,2,5,8,4,6,0,1};
//          int[] ints = {100,4,200,1,3,2};
        System.out.println(thisO.longestConsecutive(ints));
    }
}
